1. Field of the Invention
The present invention relates to garbage collection techniques in computer systems. More specifically, the present invention relates to a method and an apparatus that uses information gathered for roll back purposes by a speculatively executing thread in order to speed up the garbage collection process.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit "instruction level parallelism," in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is "speculative execution" in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
One performance drawback for programming languages, such as the Java programming language, is garbage collection. A computer system executing a program written in the Java programming language must periodically perform garbage collection to reclaim memory elements that have become de-referenced during program execution. In order to speed up this process, systems often keep track of modifications that are made to pointers during program execution. This allows a garbage collection process to identify live objects without exhaustively searching through the system heap. However, keeping track of such modifications incurs additional overhead which can greatly reduce system performance.
What is needed is a mechanism that keeps track modifications to pointers during program execution without a large amount of additional overhead.